/*************************************************************************
	> File Name: unionset.c
	> Author: Wang Bo
	> Mail: 1276106221@qq.com
	> Created Time: 2020年12月03日 星期四 23时46分15秒
 ************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include "unionset.h"

UnionSet *initUnionSet(int size) {
    UnionSet *u = (UnionSet *)malloc(sizeof(UnionSet));
    u->father = (int *)malloc(sizeof(int) * (size + 1));
    u->childs = (int *)malloc(sizeof(int) * (size + 1));
    u->size = size;
    for (int i = 1; i <= size; ++i) {
        u->father[i] = i;
        u->childs[i] = 1;
    }
    return u;
}

int find(UnionSet *u, int x) {
    /*
     * 按秩优化
     * return u->father[x] = (u->father[x] == x ? x : find(u, u->father[x]));
     */
    if (u->father[x] == x) return x;
    return find(u, u->father[x]);
}

/*
 * return 0 表示不需要合并
 */
int merge(UnionSet *u, int a, int b) {
    int fa = find(u, a), fb = find(u, b);
    if (fa == fb) return 0;
    //weighted quick union
    if (u->childs[fa] < u->childs[fb]) swap(fa, fb);
    //编程技巧
    //如果fa较小，就交换fa和fb的值，让fa恒大
    //子节点较少的合并到子节点较多的节点下面
    u->father[fb] = fa;
    u->childs[fa] += u->childs[fb];
    return 1;
}

void clearUnionSet(UnionSet *u) {
    if (u == NULL) return ;
    free(u->father);
    free(u->childs);
    free(u);
    return ;
}

